// -*- C++ -*------------------------------------------------------------------
//
//  Class:              MegaAli
//
//  Authors:            Silvio Tosatto, based on an idea by Stefano Toppo
//
//  Project Name:       BiocompUP Align
//
//  Date:               04/2002
//
//  Description:
//    This class implements the second step in assembling a maximal subset
//    of local alignments from MegaBlast output, as required to match a genomic
//    DNA sequence against its transcript(s).
//    NB: This code is being discontinued.
//
// ---------------------------------------------------------------------------

#ifndef _MEGAALI_H_
#define _MEGAALI_H_

// Includes:
#include <string>
#include <vector>
#include <Debug.h>
#include <Alignment.h>

namespace Biopool 
{

struct aPair {

  aPair(unsigned long int _x = 0, unsigned long int _y = 0) : x(_x), y(_y) {}

  unsigned long int x, y;

};

struct fragAli {

  fragAli() : data(), score(0.0) { }
  ~fragAli() { data.clear(); }

  vector<aPair> data;
  
  double score;

};


class MegaAli
{
public: 

// CONSTRUCTORS/DESTRUCTOR:
  MegaAli();
  MegaAli(const MegaAli& orig); 
  virtual ~MegaAli();

// PREDICATES:

    void writeMatrix();
    void writeStartingPoints();
    void writeFragmentAli(Alignment& ali);

// MODIFIERS:
    void readMegaBlastData(istream& input);
    void concatAlignments(Alignment& ali);

    void assignMaxAlignments(Alignment& ali);

    void copy(const MegaAli& orig);

// OPERATORS:

protected:

private:

// HELPERS: 
    void pWriteOutputData(vector<fragAli>& fragData, Alignment& ali, 
			  double bestVal);
    void pForwardRecursion(vector<fragAli>& fragData, long int& bestVal);
    void pBackwardRecursion(vector<fragAli>& fragData, long int& bestVal);
    void pRecursiveSolution(vector<fragAli>& fragData, long int& bestVal);

    void pSwapData(int l, int r);

public:
    void pSortAscending(int l, int r);
    void pDynamicSolution(vector<fragAli>& fragData, long int& bestVal);

// ATTRIBUTES:
  vector<vector<long int> > matrix;
  vector<long int> length;
  vector<long int> start1;
  vector<long int> start2;
  vector<long int> end1;
  vector<long int> end2;

  string type1;
  string type2;


public:
    unsigned long int maxGap;
    unsigned long int maxIndel;
    double threshold;
    int verbose;

};

} // namespace

#endif //_MEGAALI_H_

